package day38_76;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/16 20:02
 * @Version 1.0
 */
public class Solution {
    public String minWindow(String s, String t) {

        //使用 map 存储 t 中的字母
        Map<Character, Integer> map = new HashMap<>();

        //记录字符串t的长度，保证窗口内match的总元素个数与其相等
        int num = t.length();

        for (int i = 0; i < num; i++)
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1);

        //len记录当前最小的结果集长度 ,match为已经匹配的字母数量, resLeft记录结果集的左边界, resRight为右边界
        int len = Integer.MAX_VALUE, match = 0, resLeft = 0, resRight = 0;

        //滑动过程中的左右边界
        int left = 0, right = 0;

        while (right < s.length()) {
            //拿一个右边的更新状态
            char ch = s.charAt(right);

            if (map.containsKey(ch)) {
                //如果t中包含该字母，并且合法(不是多余的字符)，则更新匹配状态
                int val = map.get(ch) + 1;
                if (val <= 0)
                    match++;
                map.put(ch, val);
            }

            //当匹配到了所有t中包含的字母，开始缩短窗口大小
            while (match == num) {

                //如果当前窗口小于已经记录的最小子串的长度，就更新为当前子串长度，并将结果集左右边界更新
                if (right - left + 1 < len) {

                    len = right - left + 1;
                    resLeft = left;
                    resRight = right;
                }

                //从左开始收缩窗口
                char c = s.charAt(left);
                if (map.containsKey(c)) {

                    int val = map.get(c) - 1;
                    if (val < 0)
                        match--;
                    map.put(c, val);
                }

                left++;
            }

            right++;
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(resLeft, resRight + 1);
    }
}
